import java.util.*;

public class Leetcode1345 {
    public static void main(String[] args) {
        System.out.println(minJumps(new int[]{100, -23, -23, 404, 100, 23, 23, 23, 3, 404}));
    }

    public static int minJumps(int[] arr) {
        Map<Integer, List<Integer>> count = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            count.putIfAbsent(arr[i], new ArrayList<>());
            count.get(arr[i]).add(i);
        }

        int n = arr.length;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);

        int[] jumps = new int[n];
        jumps[0] = 0;


        while (!queue.isEmpty()) {
            int i = queue.poll();

            if (i - 1 >= 0 && jumps[i - 1] == 0) {
                jumps[i - 1] = jumps[i] + 1;
                queue.offer(i - 1);
            }

            if (i + 1 < n && jumps[i + 1] == 0) {
                jumps[i + 1] = jumps[i] + 1;
                queue.offer(i + 1);
            }


            List<Integer> index = count.get(arr[i]);
            for (Integer j : index) {
                if (j != i && jumps[j] == 0) {
                    jumps[j] = jumps[i] + 1;
                    queue.offer(j);
                }
            }

        }

        return jumps[n - 1];
    }
}
